//数组中的第K个最大元素
/*给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。*/
class Solution {
public:
    int qsort(vector<int>& nums, int k, int l, int r) {
        if (l >= r)
            return nums[l];
        int n = nums.size();
        int left = l - 1, i = l, right = r + 1;
        int key = getkey(nums, l, r);
        //   cout << key << '-' << k << endl;
        while (i < right) {
            if (nums[i] < key)
                swap(nums[++left], nums[i++]);
            else if (nums[i] == key)
                i++;
            else
                swap(nums[--right], nums[i]);
        }
        // for (auto& num : nums)
        //   cout << num << ' ';
        // cout << endl;
        // cout << "left:" << left << "-" << "right:" << right << endl;
        int c = r - right + 1;
        int b = right - left - 1;
        if (c >= k)
            return qsort(nums, k, right, r);
        else if (b + c >= k)
            return key;
        else
            return qsort(nums, k - (b + c), l, left);
    }
    int getkey(vector<int>& nums, int l, int r) {
        return nums[rand() % (r - l + 1) + l];
    }
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        srand((unsigned int)time(NULL));
        qsort(nums, k, 0, n - 1);
        //    for (auto& num : nums)
        //          cout << num << ' ';
        // cout << endl;
        return nums[n - k];
    }
};

//面试题 17.14. 最小K个数
class Solution {
public:
void qsort(vector<int>& nums, int k, int l, int r) {
        if (l >= r)
            return;
        int n = nums.size();
        int left = l - 1, i = l, right = r + 1;
        int key = getkey(nums, l, r);
        //   cout << key << '-' << k << endl;
        while (i < right) {
            if (nums[i] < key)
                swap(nums[++left], nums[i++]);
            else if (nums[i] == key)
                i++;
            else
                swap(nums[--right], nums[i]);
        }
        // for (auto& num : nums)
        //   cout << num << ' ';
        // cout << endl;
        // cout << "left:" << left << "-" << "right:" << right << endl;
        int a = left - l + 1;
        int b = right - left - 1;
        if (a >= k)
            qsort(nums, k, l, left);
        else if (b + a >= k)
            return;
        else
            qsort(nums, k - (b + a), right, r);
    }
    int getkey(vector<int>& nums, int l, int r) {
        return nums[rand() % (r - l + 1) + l];
    }
    vector<int> smallestK(vector<int>& nums, int k) {
        int n = nums.size();
        srand((unsigned int)time(NULL));
        qsort(nums, k, 0, n - 1);
        //    for (auto& num : nums)
        //          cout << num << ' ';
        // cout << endl;
        return {nums.begin(), nums.begin() + k};
    }
};